package leetcode.editor.cn;

import java.util.TreeSet;

public class P363MaxSumOfRectangleNoLargerThanK {
    public static void main(String[] args) {
        Solution solution = new P363MaxSumOfRectangleNoLargerThanK().new Solution();
        System.out.println(solution.maxSumSubmatrix(new int[][]{{2,2,-1}}, 3));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int rowLen = matrix.length;
            int colLen = matrix[0].length;
            int[][] prefixMatrix = new int[rowLen][colLen];
            for (int i = 0; i < rowLen; i++) {
                int sum = 0;
                for (int j = 0; j < colLen; j++) {
                    sum += matrix[i][j];
                    prefixMatrix[i][j] = sum;
                }
            }
            int findValue = Integer.MIN_VALUE;
            for (int i = 0; i < rowLen; i++) {
                for (int i1 = i; i1 < rowLen; i1++) {
                    // 行范围 i-i1
                    int rowStart = i, rowEnd = i1;
                    for (int j = 0; j < colLen; j++) {
                        for (int j1 = j; j1 < colLen; j1++) {
                            // 列范围 j-j1
                            int colStart = j, colEnd = j1;
                            int sum = 0;
                            for (int l = rowStart; l <= rowEnd; l++) {
                                sum += prefixMatrix[l][colEnd] - prefixMatrix[l][colStart] + matrix[l][colStart];
                            }
                            if (sum <= k) {
                                findValue = Math.max(findValue, sum);
                            }
                        }
                    }

                }
            }
            return findValue;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}